	package com.bupt.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import com.bupt.datastruct.TreeNode;

public class DynamicProgramming {

	/**
	 * 通配符匹配，递归算法
	 * leetcode :https://leetcode.com/problems/wildcard-matching/
	 * @param str
	 * @param pattern
	 * @param s
	 * @param p
	 * @return
	 */
	public boolean isMatchRecursion(String str, String pattern, int s, int p) {
		if (p == pattern.length())
			return s == str.length();
		// 找到第一个不是*的字符
		if (pattern.charAt(p) == '*') {
			// 找到第一个不是*的字符
			while (p < pattern.length() && pattern.charAt(p) == '*')
				p++;
			while (s < str.length()) {
				if (isMatchRecursion(str, pattern, s, p))
					return true;
				s++;
			}
			return isMatchRecursion(str, pattern, s, p);
		} else if (s < str.length()
				&& (str.charAt(s) == pattern.charAt(p) || pattern.charAt(p) == '?')) {
			return isMatchRecursion(str, pattern, s + 1, p + 1);
		}
		return false;
	}

	/**
	 * 通配符匹配，非递归做法，动态规划 时间复杂度为O（m*n）;空间复杂度优化为O（m）
	 * leetcode :https://leetcode.com/problems/wildcard-matching/
	 * ref: http://blog.csdn.net/linhuanmars/article/details/21198049
	 * ref:http://shmilyaw-hotmail-com.iteye.com/blog/2154716
	 * 通配符匹配，非递归做法，动态规划  时间复杂度为O（m*n）;
	 * 用dp[i,j]表示p[0..i-1]和是s[0...j-1]是否匹配，动态转移方程如下
	 * p[i]不是*时，dp[i+1,j+1] = dp[i,j]&& (p[i] == s[j] 或 p[i] == '?')
	 * p[i]是*的情况，因为*可以匹配0个或者多个字符串，所以只要找出dp[i][k]为true,其中 0<=k<=j,那么dp[i+1][k+1]...dp[i+1][slen]都设置true.
	 * 由于状态方程计算只用到上一行的结果，所以O(slen*plen）的空间复杂度可以优化为O(slen),空间复杂度优化后需要更新dp[0]
	 * @param s
	 * @param p
	 * @return
	 */
	public boolean isMatchDP(String s, String p) {
		if(p.length() == 0) return s.length() == 0;
		int slen = s.length();
		int plen = p.length();
		boolean[] dp = new boolean[slen+1];
		dp[0] = true;
		for(int i=0;i<plen;i++){
			if(p.charAt(i) != '*'){
				for(int j = slen-1;j>=0;j--){
					dp[j+1] = dp[j] && ( p.charAt(i) == '?' || p.charAt(i) == s.charAt(j));
				}
			} else {
				int k = 0;
				while(k<=slen && !dp[k])k++;
				for(;k<=slen;k++)dp[k] = true;
			}
			dp[0] = dp[0]&& p.charAt(i)=='*';
		}
		return dp[plen];
	}
	/**
	 * url:https://leetcode.com/problems/wildcard-matching/
	 * 通配符匹配某位大神写出的贪心算法,思路非常经典
	 * ref:http://shmilyaw-hotmail-com.iteye.com/blog/2154716
	 * @param s
	 * @param p
	 * @return
	 */
	public boolean isMathGreedy(String s,String p){
		 int ss = 0, pp = 0, match = 0, starIdx = -1;            
	        while (ss < s.length()){
	            // advancing both pointers
	            if (pp < p.length()  && (p.charAt(pp) == '?' || s.charAt(ss) == p.charAt(pp))){
	                ss++;
	                pp++;
	            }
	            // * found, only advancing pattern pointer
	            else if (pp < p.length() && p.charAt(pp) == '*'){
	                starIdx = pp;
	                match = ss;
	                pp++;
	            }
	           // last pattern pointer was *, advancing string pointer
	            else if (starIdx != -1){
	                pp = starIdx + 1;
	                match++;
	                ss = match;
	            }
	           //current pattern pointer is not star, last patter pointer was not *
	          //characters do not match
	            else return false;
	        }

	        //check for remaining characters in pattern
	        while (pp < p.length() && p.charAt(pp) == '*')
	            pp++;

	        return pp == p.length();
	}
	/**
	 * url : https://leetcode.com/problems/unique-paths/
	 * leet code 题目 uniquePaths,动态规划解法 dp[i,j] = dp[i-1,j]+dp[i,j-1]
	 * @param m
	 * @param n
	 * @return
	 */
    public int uniquePaths1(int m, int n) {
    	int[][]dp = new int[m][n];
    	if(m == 0 || n == 0){
    		return 0;
    	}
    	if(m == 1 || n == 1){
    		return 1;
    	}
    	for(int i =0;i<m;i++){
    		dp[i][0] = 1;
    	}
    	for(int j= 0;j<n;j++){
    		dp[0][j] = 1;
    	}
    	for(int i =1 ;i<m;i++){
    		for(int j = 1;j<n;j++){
    			dp[i][j] = dp[i-1][j] + dp[i][j-1]; 
    		}
    	}
    	return dp[m-1][n-1];
    }
    /**
     * url :https://leetcode.com/problems/unique-paths/
     * leetCode题目 uniquePaths 解决办法2 
     * 分析：从位置（0,0）走到(m-1,n-1)总共需要 (m-1) + (n -1),其中向下走n-1步，转化为组合问题，result = C(m+n-2,n-1);
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths2(int m, int n) {
    	int N = m+n-2;
    	int k = n-1;
    	double res = 0;
    	for(int i = N-k+1;i<=N;i++){
    		res = res*i;
    		res = res/(N-i+1);
    	}
    	return (int)res;	
    }
	/**
	 * url : https://leetcode.com/problems/unique-paths-ii/
	 * leet code 题目 uniquePaths II,只需要将障碍物忽略掉  基本动态规划方程仍为 dp[i,j] = dp[i-1,j] +dp[i,j-1],不过需要去除那些障碍物的计数，进行判断
	 * @param m
	 * @param n
	 * @return
	 */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    	int m = obstacleGrid.length;
    	int n = obstacleGrid[0].length;
    	int[][]dp = new int[m][n];
    	for(int i =0;i<m;i++){
    		if(obstacleGrid[i][0] == 1){
    			break;
    		}
    		dp[i][0] = 1;
     	}
    	for(int j= 0;j<n;j++){
    		if(obstacleGrid[0][j] == 1){
    			break;
    		}
    		dp[0][j] = 1;
    	}
    	for(int i =1 ;i<m;i++){
    		for(int j = 1;j<n;j++){
    			if(obstacleGrid[i][j] == 1){
    				continue;
    			}
    			if(obstacleGrid[i-1][j] != 1){
    				dp[i][j] += dp[i-1][j]; 
    			}
    			if(obstacleGrid[i][j-1] != 1){
    				dp[i][j] += dp[i][j-1]; 
    			}
    		}
    	}
    	return dp[m-1][n-1];
    }
    /**
     * url : https://leetcode.com/problems/unique-binary-search-trees/
     * 问题描述：求1..n的二分查找树的个数
     * f(k,n)表示以k为根节点，并且总节点数为n的BST计数，dp[n]表示从1..n个节点的BST计数
     * 有 f(k,n) = dp[k-1]*dp[n-k],dp[n] = sum(f(i,n)); 1<=i<=n
     * @param n
     * @return
     */
    public int numTrees(int n) {
        if(n == 0) return 0;
        int[] dp = new int[n+1];
        for(int i = 1;i<=n;i++){
        	for(int j = 1; j<=i;j++){
        		dp[i] += dp[j-1]*dp[i-j];
        	}
        }
        return dp[n];
    }
    /**
     * url :https://leetcode.com/problems/unique-binary-search-trees-ii/
     * Unique Binary Search Trees II 
     * 递归解决问题，简单，但是效率低下
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) {
        return this.help(1,n);
    }
    /**
     * Unique Binary Search Trees II 递归函数
     * @param left
     * @param right
     * @return
     */
    public List<TreeNode> help(int left,int right){
    	List<TreeNode> res = new ArrayList<TreeNode>();
    	if(left > right){
    		res.add(null);
    		return res;
    	}
    	if(left == right){
    		res.add(new TreeNode(left));
    		return res;
    	}
    	for(int i = left ;i<=right;i++){
    		List<TreeNode> leftList = help(left, i-1);
    		List<TreeNode> rightList = help(i+1, right);
    		for(int j = 0 ;j<leftList.size();j++){
    			for(int k =0 ;k<rightList.size();k++){
    				TreeNode root = new TreeNode(i);
    				root.left = leftList.get(j);
    				root.right = rightList.get(k);
    				res.add(root);
    			}
    		}
    	}
    	return res;
    }
    /**
     * 数塔最小路径问题
     * url: https://leetcode.com/problems/triangle/
     * 从下 向上进行动态规划
     * @param triangle
     * @return
     */
	public int minimumTotal(List<List<Integer>> triangle) {
		if(triangle.size() < 1) return 0;
		if(triangle.size() == 1) return triangle.get(0).get(0);
		int[] min = new int[triangle.size()-1];
		for(int i =0 ;i<min.length;i++){
			min[i] = triangle.get(triangle.size()-1).get(i);
		}
		for(int j = triangle.size() - 2 ;j>=0;j--){
			for(int i = 0 ;i<j+1;i++){
				min[i] = Math.min(min[i],min[i+1]) + triangle.get(i).get(j);
			}
		}
		return min[0];
	}
	/**
	 * Scramble String 
	 * url: https://leetcode.com/problems/scramble-string/
	 * dp[i][j][len]表示从s1中第i个字符和s2中第j个字符长度为len的子串是不是Scramble String
	 * ref :https://leetcode.com/problems/scramble-string/
	 * @param s1
	 * @param s2
	 * @return
	 */
	public boolean isScramble(String s1, String s2) {
		if (s1.length() == 0)
			return s2.length() == 0;
		int slen = s1.length();
		boolean[][][] dp = new boolean[slen][slen][slen + 1];
		// 初始化
		for (int i = 0; i < slen; i++) {
			for (int j = 0; j < slen; j++) {
				dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
			}
		}
		for (int len = 2; len <= slen; len++) {
			for (int i = 0; i < slen - len + 1; i++) {
				for (int j = 0; j < slen - len + 1; j++) {
					for (int k = 1; k < len; k++) {
						if ((dp[i][j][k] && dp[i + k][j + k][len - k])
								|| (dp[i][j + len - k][k] && dp[i + k][j][len - k])) {
							dp[i][j][len] = true;
						}
					}
				}
			}
		}
		return dp[0][0][s1.length()];
	}	
	/**
	 * 题目： Maximum Subarray 
	 * url:https://leetcode.com/problems/maximum-subarray/
	 * 求整形数组最大子串和，考烂了的题目
	 * @param A
	 * @return
	 */
    public int maxSubArray(int[] A) {
    	int thisSum = 0,maxSum = Integer.MIN_VALUE;
    	for(int i = 0;i<A.length;i++){
    		thisSum += A[i];
    		if(thisSum > maxSum)
    			maxSum = thisSum;
    		if(thisSum < 0)
    			thisSum = 0;
    	}
    	return maxSum;
    }
    /**
     * 题目：Minimum Path Sum 
     * url:https://leetcode.com/problems/minimum-path-sum/
     * M*N的正整数格子，从左上角到右下角，求所经过的最小路径和
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int [][] dp = new int[row][col];
        for(int i = 0; i<row;i++){
        	for(int j=0;j<col;j++){
        		if( i > 0 && j >0){
        			dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
        		}else if(i>0){
        			dp[i][j] = grid[i][j] + dp[i-1][j];
        		}else if(j>0){
        			dp[i][j] = grid[i][j] + dp[i][j-1];
        		}else {
        			dp[i][j] = grid[i][j];
        		}
        	}
        }
        return dp[row-1][col-1];
    }
    
    /**
	 * leetCode题目 买股票问题解决办法1
	 * url : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
	 * BestTimeToBuy And Sell Stock I ,dp解法 dp[i+1] = max{dp[i],prices[i+1] -
	 * leastPrice}
	 * 
	 * @param prices
	 * @return
	 */
	public int maxProfitIsolve1(int[] prices) {
		if (prices.length <= 1) {
			return 0;
		}
		int iProfit = 0, leastPrice = prices[0], i = 1;
		while (i < prices.length) {
			if (prices[i] < leastPrice) {
				leastPrice = prices[i];
			}
			iProfit = iProfit > prices[i] - leastPrice ? iProfit : prices[i]
					- leastPrice;
			i++;
		}
		return iProfit;
	}

	/**
	 * leetCode题目，买股票问题I，解决办法2
	 * url : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
	 * 买股票问题1  求出prices中任意所有的prices[i] - prices[i-1] ,存入diff数组，问题转化为求diff数组的最大字数组和的问题
	 * @param prices
	 * @return
	 */
	public int maxProfitISolve2(int[] prices) {
		if (prices.length <= 1) {
			return 0;
		}
		int diff[] = new int[prices.length - 1];
		for (int i = 1; i < prices.length; i++) {
			diff[i - 1] = prices[i] - prices[i - 1];
		}
		int thisSum = 0, maxSum = 0, i = 0;
		while (i < prices.length) {
			thisSum += diff[i];
			if (thisSum > maxSum) {
				maxSum = thisSum;
			} else if (thisSum < 0) {
				thisSum = 0;
			}
			i++;
		}
		return maxSum;
	}
	/**
	 * url : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
	 * 买股票问题2  思路：求出所有的上升区间，相加即可得到结果
	 * @param prices
	 * @return
	 */
	public int maxProfitIISolve1(int[] prices){
		if (prices.length <= 1) {
			return 0;
		}
		int profit = 0,i = 0,len = prices.length;
		while(i< len-1){
			int buy,sell;
			while(i+1<len && prices[i] > prices[i+1]) i++;
			buy = i;
			while(i+1<len && prices[i] <= prices[i+1]) i++;
			sell = i;
			profit += prices[sell] - prices[buy];
		}
		return profit;
	}
	/**
	 * url : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
	 * 买股票问题3  两次遍历，求出从前到后的dpHead[i]和从后到前的dpTail[i]
	 * @param prices
	 * @return
	 */
	public int maxProfitIIISolve(int[] prices){
		if (prices.length <= 1) {
			return 0;
		}
		int[] dpFromHead = new int[prices.length];
		int[] dpFromTail = new int[prices.length];
		int lowest = prices[0];
		int highest = prices[prices.length -1 ];
		dpFromHead[0] = 0;
		dpFromTail[prices.length - 1] = 0;
		for(int i = 1 ; i < prices.length;i++){
			if(prices[i] < lowest){
				lowest = prices[i];
			}
			dpFromHead[i] = dpFromHead[i-1]>prices[i] - lowest?dpFromHead[i-1]:prices[i] - lowest;
			if(prices[prices.length- 1 - i] > highest){
				highest = prices[prices.length -1-i];
			}
			dpFromTail[prices.length - 1 -i] = dpFromTail[prices.length-i] > highest - prices[prices.length - 1 -i]?dpFromTail[prices.length -i]:highest - prices[prices.length - 1 -i]; 
		}
		int max = 0;
		for (int i= 0;i<prices.length;i++){
			int currentRight = i+1 >= prices.length ? 0 : dpFromTail[i+1];
			if(dpFromHead[i] + currentRight > max){
				max = dpFromHead[i] + currentRight;
			}
		}
		return max;
	}
    /**
     * 问题描述，prices为股票价格数组，在最大操作数为k的情况下求出最大收益（手中最多持有一支股票）
     * 买卖股票问题最终版本也是普适性做法，买股票1，2，3问题分别为k = 1,k = ∞和k = 2的特殊版本
     * 该解答对于如何将二维动态规划状态数组转化为一维状态数组的解法也非常经典
     * ref : http://blog.csdn.net/linhuanmars/article/details/23236995#java
     * @param prices
     * @return
     */
    public int maxProfitIV(int k, int[] prices){
    	int maxProfit = 0;
    	if(k>= prices.length){
    		for(int i = 0;i<prices.length-1;i++){
    			maxProfit += prices[i+1] - prices[i]>0?prices[i+1]-prices[i]:0; 
    		}
    		return maxProfit;
    	}
    	int[] global = new int[k+1],local = new int[k+1];
    	for(int i = 0;i<prices.length-1;i++){
    		int diff = prices[i+1] - prices[i];
    		for(int j = k;j>=1;j--){
    			local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);  
                global[j] = Math.max(local[j],global[j]);  
    		}
    	}
    	return global[k];
    }
    /**
     * Decode Ways 解码字符串
     * A message containing letters from A-Z is being encoded to numbers using the following mapping:
     * 'A' -> 1 ，'B' -> 2，...，'Z' -> 26
     * For example,Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).		         	 * url :https://leetcode.com/problems/decode-ways/
	 * 动态方程为斐波那契数列的变种
     * @param s
     * @return
     */
	public int numDecodings(String s) {
	    if (s.length() == 0 || s.charAt(0) == '0') {
			return 0;
		}
		int[] dp = new int[s.length()];
		dp[0] = 1;
		if(s.length() == 1){
			return dp[0];
		}
		//求解dp[1]
		int s0 = Integer.parseInt(s.substring(0,2));
		if(s0 <= 26 && s0 >= 10){
			dp[1]++;
		}
		if(s.charAt(1) >= '1'){
			dp[1]++;
		}
		if(dp[1] < 1){
			return 0;
		}
		for(int i =2 ;i<s.length();i++){
			int ss = Integer.parseInt(s.substring(i-1,i+1));
			if(ss % 10 != 0){
				dp[i] = dp[i-1];
			}
			if(ss <= 26 && ss >= 10){
				dp[i] += dp[i-2];
			}
			if(dp[i] < 1){
				return 0;
			}
		}
		return dp[s.length()-1];
	}
	/**
	 * leetCode word break题目，使用动态规划算法进行计算，dp[i]表示[0...i]是否可以分解成集合的字符串集合
	 * 动态规划方程 dp[i] ||= (dp[k] && set.contains(s[k+1...i])( 0<k<i) 
	 * url : https://leetcode.com/problems/word-break/
	 * @param s
	 * @param dict
	 * @return
	 */
    public boolean wordBreakIsolove1(String s, Set<String> dict) {
        Boolean[] dp = new Boolean[s.length()];
        for(int i = 0 ;i<dp.length;i++){
        	dp[i] = false;
        }
        for(int i = 0;i<s.length();i++){
        	for(int j = i;j>=0;j--){
        		String sij = s.substring(j,i+1);
        		if(dict.contains(sij) && (j==0 || dp[j-1] == true)){
        			dp[i] = true;
        		}
        	}
        }
        return dp[s.length()-1];
    }
    /**
     *  LeetCode: Distinct Subsequences（不同子序列的个数）
     *  使用动态规划思路
     *  动态规划，设dp[i][j]是从字符串S[0...i]中删除几个字符得到字符串T[0...j]的不同的删除方法种类，有上面递归的分析可知，动态规划方程如下
     *  如果S[i] = T[j], dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
	 *  如果S[i] 不等于 T[j], dp[i][j] = dp[i-1][j]
	 *  初始条件：当T为空字符串时，从任意的S删除几个字符得到T的方法为1
	 *  ref ： http://www.cnblogs.com/TenosDoIt/p/3440022.html
     * @param S
     * @param T
     * @return
     */
    public int numDitinct(String S,String T){
    	int[][]dp = new int[T.length()+1][S.length()+1];
    	for(int i = 0; i<S.length()+1;i++){
    		dp[0][i] = 1;
    	}
    	for (int i = 1;i<T.length()+1;i++){
    		for (int j =1;j<S.length()+1;j++){
    			dp[i][j] = dp[i][j-1];
    			if(S.charAt(j-1) == T.charAt(i-1)){
    				dp[i][j] += dp[i-1][j-1];
    			}
    		}
    	}
    	return dp[T.length()][S.length()];
    }
     
	/**
	 * 最大子数组积
	 * url : https://leetcode.com/problems/maximum-product-subarray/
	 * 思路：动态规划，维持一个以当前整数作为结尾的子数组的局部最大值和一个局部最小值，最后维持一个全局最大值
	 * 状态转移方程为：
	 * 对A[i]而言，maxLocal = max { minLocal *A[i] , maxLocal *A[i] ,A[i]}
	 * minLocal = min { minLocal * A[i],maxLocal * A[i],A[i]}
	 * global = max {maxLocal , global }
	 * @param A
	 * @return
	 */
	public int maxProduct(int[] A) {
	    if(A==null || A.length==0)
	        return 0;
	    if(A.length == 1)
	        return A[0];
	    int max_local = A[0];
	    int min_local = A[0];
	    int global = A[0];
	    for(int i=1;i<A.length;i++)
	    {
	        int max_copy = max_local;
	        max_local = Math.max(Math.max(A[i]*max_local, A[i]), A[i]*min_local);
	        min_local = Math.min(Math.min(A[i]*max_copy, A[i]), A[i]*min_local);
	        global = Math.max(global, max_local);
	    }
	    return global;
	}
	/**
	 * 最小回文子串切割数目
	 * Given a string s, partition s such that every substring of the partition is a palindrome.
     * Return the minimum cuts needed for a palindrome partitioning of s.
     * path[i][j]表示字符串s[i...j]是否为回文字符串
     * dp[i]表示s[i...len-1]切割成回文子串的最小切割数目
     * dp[i]初始化为 len-1-i(切割为一个个的字符)
     * 状态转移方程为 dp[i] = min{dp[j+1] + 1 | path[i][j] , i<=j<=len-2} ,如果path[i..len-1]为真，dp[i] = 0; 无需切割 
     * url : https://leetcode.com/problems/palindrome-partitioning-ii/
     * 思路 ： 动态规划
	 * @param s
	 * @return
	 */
    public int minCut(String s) {
        boolean [][] path = new boolean[s.length()][s.length()];
        int []dp = new int[s.length()];
        dp[s.length()-1] = 0;
        for(int i = s.length()-1 ; i>= 0 ;i--){
        	dp[i] = s.length() - 1 - i;
        	for(int j = i;j < s.length();j++){
        		if(s.charAt(i) == s.charAt(j) && (j- i < 2 || path[i+1][j-1])){
        			path[i][j] = true;
        			if(j == s.length()-1){
        				dp[i] = 0;
        			}else {
        				dp[i] = (dp[j+1]+1)<dp[i]?dp[j+1]+1:dp[i];
        			}
        		}
        	}
        }
        return dp[0];
    }
    /**
     * 递归求解Regular Expression Matching 匹配
     * @param s
     * @param p
     * @return
     */
    public boolean  isMatchRegularExpressionMatchingRecurse(String s,String p){
    	return isMatchHelper(s, p, 0, 0);
    }
    /**
     * 递归函数体
     * @param s
     * @param p
     * @param i
     * @param j
     * @return
     */
	public boolean isMatchHelper(String s, String p, int i, int j) {
		// 判断是否i,j已经匹配完成
		if (j == p.length())
			return i == s.length();
		// p[j+1]不是*时，判断s[i]是否等于p[j]
		if (j == p.length() - 1 || p.charAt(j + 1) != '*') {
			if (i < s.length()
					&& (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i))) {
				return isMatchHelper(s, p, i + 1, j + 1);
			} else {
				return false;
			}
		}
		// p[j+1]是*的时候。如果s[i]...s[i+k]都等于p[j](或p[j] == '.')则
		// s[i..len]...s[i+k+1..len]和p[j+2..len]都有可能匹配,如果有一个匹配成功，就会返回true;
		while (i < s.length()
				&& (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
			if (isMatchHelper(s, p, i, j + 2))
				return true;
			i++;
		}
		// 继续递归匹配s[i..len],[j+2..len]
		return isMatchHelper(s, p, i, j + 2);
	}
	/**
	 * 常规表达式匹配 我只能说 尽力了，真想不出来
	 * ref :http://blog.csdn.net/linhuanmars/article/details/21145563
	 * url :https://leetcode.com/problems/regular-expression-matching/
	 * 动态规划解法
	 * @param s
	 * @param p
	 * @return
	 */
	public boolean isMatch(String s, String p) {
		if (s.length() == 0 && p.length() == 0)
			return true;
		if (p.length() == 0)
			return false;
		boolean[][] res = new boolean[s.length() + 1][p.length() + 1];
		res[0][0] = true;
		for (int j = 0; j < p.length(); j++) {
			if (p.charAt(j) == '*') {
				if (j > 0 && res[0][j - 1])
					res[0][j + 1] = true;
				if (j < 1)
					continue;
				if (p.charAt(j - 1) != '.') {
					for (int i = 0; i < s.length(); i++) {
						if (res[i + 1][j] || j > 0 && res[i + 1][j - 1]
								|| i > 0 && j > 0 && res[i][j + 1]
								&& s.charAt(i) == s.charAt(i - 1)
								&& s.charAt(i - 1) == p.charAt(j - 1))
							res[i + 1][j + 1] = true;
					}
				} else {
					int i = 0;
					while (j > 0 && i < s.length() && !res[i + 1][j - 1]
							&& !res[i + 1][j])
						i++;
					for (; i < s.length(); i++) {
						res[i + 1][j + 1] = true;
					}
				}
			} else {
				for (int i = 0; i < s.length(); i++) {
					if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')
						res[i + 1][j + 1] = res[i][j];
				}
			}
		}
		return res[s.length()][p.length()];
	}
	/**
	 * leetcode 题目，s3是否由s1和s2序列组合起来
	 * url :https://leetcode.com/problems/interleaving-string/
	 * @param s1
	 * @param s2
	 * @param s3
	 * @return
	 */
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s3.length() != s1.length() + s2.length()){
        	return false;
        }
        String maxWord = s1.length() > s2.length() ? s1:s2;
        String minWord = s1.length() > s2.length() ? s2:s1;
        //空间复杂度优化优化
        boolean []res = new boolean[minWord.length()+1];
        res[0] = true;
        //初始化，0
        for(int i = 0 ;i<minWord.length();i++){
        	res[i+1] = res[i] && s3.charAt(i) == minWord.charAt(i);
        }
        for(int i = 0 ;i<maxWord.length();i++){
        	res[0] = res[0] && s3.charAt(i) == maxWord.charAt(i);
        	for(int j = 0; j<minWord.length();j++){
        		res[j+1] = s3.charAt(i+j+1) == minWord.charAt(j) && res[j] || s3.charAt(i+j+1) == maxWord.charAt(i) && res[j+1];
        	}
        }
        return res[minWord.length()];
    }
	/**
     * 最长合法括号匹配
     * Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
     * For "(()", the longest valid parentheses substring is "()", which has length = 2.
     * ref :http://blog.csdn.net/linhuanmars/article/details/20439613
     * url : https://leetcode.com/problems/longest-valid-parentheses/
     * 使用栈进行序列匹配
     * @param s
     * @return
     */
	public int longestValidParentheses(String s) {
		if(s.length() <= 1) return 0;
		LinkedList<Integer> stack = new LinkedList<Integer>();
		int max = 0,start = 0;
		for(int i = 0 ;i<s.length();i++){
			//左括号进栈
			if(s.charAt(i) == '('){
				stack.push(i);
			//右括号	
			}else {
				//栈为空，表示前面的已经匹配或者前面无元素,变更起始位置
				if(stack.isEmpty()){
					start = i + 1;
				}else {
					//弹出栈顶元素
					stack.pop();
					//弹出栈顶元素之后如果为空,当前的max为i-起始位置+1，否则为当前元素所在位置-栈顶元素的
					max = stack.isEmpty()?Math.max(max, i-start + 1):Math.max(max, i-stack.peek());
				}
			}
		}
		return max;
	}
	/**
	 * Leet Code Dungeon Game题目
	 * url :https://leetcode.com/problems/dungeon-game/
	 * 思路其实和unique path差不多，只不过需要从右下角向左上角开始递归!,并且要进行一定的预处理
	 * @param dungeon
	 * @return
	 */
    public int calculateMinimumHP(int[][] dungeon) {
    	int m = dungeon.length;
    	int n = dungeon[0].length;
    	int[][] res = new int[m][n];
    	res[m-1][n-1] = dungeon[m-1][n-1] > 0? 0 :-dungeon[m-1][n-1];
    	//初始化最后一行
    	for(int i = n-2;i>=0 ;i--){
    		res[m-1][i] = dungeon[m-1][i] - res[m-1][i+1]> 0? 0:res[m-1][i+1] - dungeon[m-1][i];
    	}
    	//初始化最后一列
    	for(int j = m-2;j>=0 ;j--){
    		res[j][n-1] = dungeon[j][n-1] - res[j+1][n-1] >0? 0:res[j+1][n-1] - dungeon[j][n-1];
    	}
    	//从右下角向左上角递归；
    	for(int j = m-2;j >=0;j--){
    		for(int i = n-2;i>=0;i--){
    			res[j][i] = dungeon[j][i] - Math.min(res[j+1][i], res[j][i+1])>0 ? 0 :Math.min(res[j+1][i], res[j][i+1]) - dungeon[j][i];
    		}
    	}
    	return res[0][0]+1;
    }
    /**
     * url:https://leetcode.com/problems/house-robber/
     * 动态规划方程： res[i] = max(res[i-1],res[i-2]+num[i])
     * @param num
     * @return
     */
    public int rob(int[] num) {
       if(num.length == 0)return 0;
       if(num.length == 1)return num[0];
       int res[] = new int[num.length];
       res[0] = num[0];
       res[1] = Math.max(num[0],num[1]);
       for(int i = 2;i<num.length;i++){
    	   res[i] = Math.max(res[i-1],num[i]+res[i-2]);
       }
       return res[num.length-1];
    }
    /**
     * 字符串之间的最小距离
     * ref:http://blog.csdn.net/linhuanmars/article/details/24213795
     * url :https://leetcode.com/problems/edit-distance/
     * 将空间复杂度优化为O（min(m,n)）时间复杂度位O(mn)
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        if(word1.length() == 0) return word2.length();
        if(word2.length() == 0) return word1.length();
        String maxWord = word1.length() > word2.length()?word1:word2;
        String minWord = word1.length() > word2.length()?word2:word1;
        int res[] = new int[minWord.length()+1];
        for(int i = 0;i <= maxWord.length();i++){
        	res[i] = i;
        }
        for(int i = 0;i<maxWord.length();i++){
        	int newRes[] = new int[minWord.length()+1];
        	newRes[0] = i+1;
        	for(int j = 0;j<minWord.length();j++){
        		if(minWord.charAt(j) == maxWord.charAt(i)){
        			newRes[j+1] = res[j];
        		}else {
        			newRes[j+1] = Math.min(Math.min(res[j],res[j+1]),newRes[j])+1;
        		}
        	}
        	res = newRes;
        }
        return res[minWord.length()];
    }
	/**
	 * 求包含0、1的二维矩阵围成的1矩形的最大面积
	 * 题号：85
	 * @param matrix
	 * @return
	 */
    public int maximalRectangle(char[][] matrix) {
    	if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
    	int m = matrix.length;
    	int n = matrix[0].length;
    	List<Integer> dp = new LinkedList<Integer>();
    	for(int i = 0; i< n;i++){
    		dp.add(0);
    	}
    	int maxArea = 0;
    	for(int i = 0;i<m;i++){
    		for(int j = 0;j<n;j++){
    			int height = matrix[i][j] - '0' == 0 ? 0:dp.get(j)+1;
    			dp.set(j,height);
    		}
    		maxArea = Math.max(maxArea,maxRectangleHelper(dp));
    	}
    	return maxArea;
    }
    /**
     * 求直方图组成的矩形最大面积 
     * see : {@link com.bupt.leetcode.StackProblem}
     * 的   public int largestRectangleArea(int[] height) 方法
     * @param heights
     * @return
     */
    private int maxRectangleHelper(List<Integer> heights){
    	if(heights.size() == 0) return 0;
    	heights.add(0);
    	int i = 0,maxArea = 0;
    	LinkedList<Integer> stack = new LinkedList<Integer>();
    	while(i<heights.size()){
    		if(stack.isEmpty() || heights.get(i) >= heights.get(stack.peek())){
    			stack.push(i++);
    		}else {
    			int top = stack.pop();
    			int curArea = heights.get(top) * (stack.isEmpty()?i:i-stack.peek()-1);
    			maxArea = Math.max(curArea, maxArea);
    		}
    	}
    	heights.remove(heights.size()-1);
    	return maxArea;
    }
}
